import { defaultToString } from '../util';
import { ValuePair } from './models/value-pair';

/**
 * HashTable：Dictionary类的一种散列表实现，也叫HashMap。区别就是HashTable用hash值作为键，并且可以相同key不同value
 * 散列算法的作用是尽可能快地在数据结构中找到一个值（知道值的具体位置，能快速检索到该值）
 * js语言内部就是使用散列表来表示每个对象，对象的每个属性和方法（成员）被储存为key对象类型，每个key指向对应的对象成员
 */
export default class HashTable<K, V> {
    private _toStrFn: (key: K) => string;
    private _table: { [key: string]: ValuePair<K, V> };
    constructor(toStrFn: (key: K) => string = defaultToString) {
        this._table = {};
        this._toStrFn = toStrFn;
    }
    /**
     * 散列函数1
     */
    private loseloseHashCode(key: K): number {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this._toStrFn(key);
        let hash = 0;
        for (let i = 0, le = tableKey.length; i < le; i ++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 散列函数2
     * 一个表现良好的散列函数由几个方面构成：
     * 插入和检索元素的时间（即性能），以及较低的冲突可能性。
     */
    /* private djb2HashCode(key: K) {
        const tableKey = this._toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i ++) {
            hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
    } */
    /**
     * 得到key对应的hash值，这个hash值会作为hashtable的键
     */
    public hashCode(key: K): number {
        // return this.djb2HashCode(key); // 使用更好的散列函数
        return this.loseloseHashCode(key);
    }
    /**
     * 向HashTable中添加新元素。如果键已经存在则会被新的值覆盖
     */
    public put(key: K, value: V): boolean {
        if (key != null && value != null) {
            const tableKey: number = this.hashCode(key);
            this._table[tableKey] = new ValuePair<K, V>(key, value);
            return true;
        }
        return false;
    }
    /**
     * 通过以键值作为参数查找对应的值并返回
     */
    public get(key: K): V {
        if (key != null) {
            const valuePair = this._table[this.hashCode(key)];
            return !valuePair ? undefined : valuePair.value;
        }
        return undefined;
    }
    /**
     * 通过键来删除字典中对应的键值对
     */
    public remove(key: K): boolean {
        if (key != null) {
            const tableKey: number = this.hashCode(key);
            const valuePair: ValuePair<K, V> = this._table[tableKey];
            if (valuePair != null) {
                delete this._table[tableKey];
                return true;
            }
            return false;
        }
        return false;
    }
    /**
     * 返回hashtable
     */
    public getTable(): { [key: string]: ValuePair<K, V> } {
        return this._table;
    }
    /**
     * hashtable大小
     */
    public size(): number {
        return Object.keys(this._table).length;
    }
    /**
     * hashtable是否为空
     */
    public isEmpty(): boolean {
        return this.size() === 0;
    }
    /**
     * 清空hashtable
     */
    public clear() {
        this._table = {};
    }
    /**
     * 返回hashtable的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this._table);
        let objString = `{${keys[0].toString()} => ${this._table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i ++) {
            objString = `${objString},{${keys[i].toString()} => ${this._table[keys[i]].toString()}}`;
        }
        return objString;
    }
}
